package BFS;


import 工具包.*;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @Author: biubiu0002
 * @Date: 2021-03-31 20:01
 **/
public class 二叉树的最小高度 {
    int BFSModel(Node start,Node target){
        //核心：队列
        Queue<Node> q = new LinkedList<>();
        //避免走回头路
        Set<Node> visited= new HashSet<>();
        q.offer(start);//把起点加入到路径
        int step = 0;
        while(!q.isEmpty()){
            int sz = q.size();
            /*将当前队列中的元素向四周扩散*/
            for(int i =0;i<sz;i++){
                //poll没元素了会返回null
                //remove没元素了会抛NullPointerException
                Node cur = q.poll();
                //!!!!这里判断cur是否到达终点
                if(cur.isTarget()){
                    return step;
                }
                //将cur的相邻节点加入队列
                for(Node x:cur.adjs){
                    if(!visited.contains(x)){
                        q.offer(x);
                        visited.add(x);
                    }
                }
            }
            //划重点！！！更新步数在这里
            step++;

        }
        return step;
    }

    public int minDepth(TreeNode root) {
        if(root==null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int height = 1;
        while(!q.isEmpty()){
            //将当前队列中的【所有】节点向四周扩散
            int sz = q.size();

            for(int i=0;i<sz;i++){
                TreeNode cur = q.poll();
                if(cur.left==null&&cur.right==null)
                    return height;
                if(cur.left!=null)
                    q.offer(cur.left);
                if(cur.right!=null)
                    q.offer(cur.right);
            }
            height++;
        }
        return height;
    }

    public static void main(String[] args) {

    }



    class Node{
        Node[] adjs;

        boolean isTarget(){
            return false;
        }

    }
}
